package code1;

import java.util.Arrays;

/**
 * @author noob
 * @version 1.0
 * @date 2021/3/16 14:27
 * 快排--插入排序优化--因为使用插入排序法优化的原理是，对于小规模的数组，使用插入排序法更快。
 *
 * jVM设置：-Xss128m
 *
 */
public class QuickSort2 {

    public static <E extends Comparable<E>>  void sort(E[] arr) {
        quicksort(arr,0,arr.length-1);
    }


    public static <E extends Comparable<E>>   void quicksort(E[] arr,int left,int right){

//        if(left > right) {
//            return; //递归出口
//        }

        if(right - left <=15){
            InsertionSort(arr,left,right);
            return;
        }


        int p=partition(arr,left,right);
        quicksort(arr,left,p-1);
        quicksort(arr,p+1,right);


    }

    private static <E extends Comparable<E>> void InsertionSort(E[] arr, int left, int right) {

        for (int i = left; i <=right ; i++) {
            E t = arr[i];
            int j;
            for ( j = i; j -1 >= left &&  t.compareTo(arr[j-1]) <0 ; j--) {
                arr[j]=arr[j-1];
            }
            arr[j] = t;
        }


    }

    private static<E extends Comparable<E>> int partition(E[] arr, int left, int right) {

        E v = arr[left];
        int j  = left;
        for (int i = left+1; i <= right;i++ ) {
            if (arr[i].compareTo(v) < 0){
                j++;
                exchange(arr,i,j);
            }
//            大于就直接i++
        }
        //最后交换
        exchange(arr,left,j);

        return j;

    }

    private static  <E extends Comparable<E>> void exchange(E[] arr, int i, int j) {
        E temp=arr[i];
        arr[i] =arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {


        int[]  dataSize = {100000,1000000};
        for(int n:dataSize){
//            Integer[] array = ArrayGenerator.generateRandomArray(n, n);
            Integer[] array = ArrayGenerator.generateOrderedArray(n);
            Integer[]  copy = Arrays.copyOf(array,array.length);
            SortHelper.sortTest("QuickSort",array);
            SortHelper.sortTest("QuickSort2",copy);

            System.out.println("--------------------------------");
        }

        /**
         * 对于完全有序的数据性能不佳
         */

    }


}
